import java.util.Stack;

/**
 * 739. 每日温度
 * https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution2 {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ret = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++) {
            if(stack.empty() || temperatures[i] < temperatures[stack.peek()]) {
                stack.push(i);
            } else {
                // temperatures[i] >= temperatures[stack.peek()]
                // 弹出栈顶元素，当前元素大于栈顶元素
                while(!stack.empty() && temperatures[i] > temperatures[stack.peek()]) {
                    int tmp = stack.pop();
                    ret[tmp] = i - tmp;
                }
                stack.push(i);
            }
        }
        return ret;
    }
}